Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Linearly \(\chi \)-Bounding \((P_6,C_4)\)-Free Graphs
verfasst von : Serge Gaspers, Shenwei Huang
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given two graphs \(H_1\) and \(H_2\), a graph G is \((H_1,H_2)\)-free if it contains no subgraph isomorphic to \(H_1\) or \(H_2\). Let \(P_t\) and \(C_s\) be the path on t vertices and the cycle on s vertices, respectively. In this paper we show that for any \((P_6,C_4)\)-free graph G it holds that \(\chi (G)\le \frac{3}{2}\omega (G)\), where \(\chi (G)\) and \(\omega (G)\) are the chromatic number and clique number of G, respectively. Our bound is attained by \(C_5\) and the Petersen graph. The new result unifies previously known results on the existence of linear \(\chi \)-binding functions for several graph classes. Our proof is based on a novel structure theorem on \((P_6,C_4)\)-free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time 3/2-approximation algorithm for coloring \((P_6,C_4)\)-free graphs. Our algorithm computes a coloring with \(\frac{3}{2}\omega (G)\) colors for any \((P_6,C_4)\)-free graph G in \(O(n^2m)\) time.