Sökning: "Ruth Bosse"

Hittade 1 uppsats innehållade orden Ruth Bosse.

  1. 1. On Minimal Non-(2, 1)-Colorable Graphs

    Master-uppsats, Stockholms universitet/Matematiska institutionen

    Författare :Ruth Bosse; [2017]
    Nyckelord :Graph coloring;

    Sammanfattning : A graph is (2, 1)-colorable if it allows a partition of its vertices into two classes such that both induce graphs with maximum degree at most one. A non-(2, 1)-colorable graph is minimal if all proper subgraphs are (2, 1)-colorable. We prove that such graphs are 2-edge-connected and that every edge sits in an odd cycle. LÄS MER