Vizing bound for the chromatic number on some graph classes

DOI10.1007/s00373-015-1651-1zbMath1342.05040OpenAlexW2284570459MaRDI QIDQ2631086

T. Karthick, Frédéric Maffray

Publication date: 28 July 2016

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-015-1651-1

zbMATH Keywords

chromatic numberdiamond-free graph\(\chi\)-bounded class\(P_6\)-free

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items (16)

Colouring graphs with no induced six-vertex path or diamond ⋮ Chromatic bounds for the subclasses of \(pK_2\)-free graphs ⋮ The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor ⋮ On the chromatic number of (\(P_6\), diamond)-free graphs ⋮ THE CHROMATIC NUMBER OF -FREE GRAPHS ⋮ On graphs with no induced five‐vertex path or paraglider ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques ⋮ Bounds for the chromatic number of some \(pK_2\)-free graphs ⋮ On the chromatic number of (P5,dart)-free graphs ⋮ Colouring of \((P_3 \cup P_2)\)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Chromatic bounds for some classes of \(2 K_2\)-free graphs ⋮ Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded ⋮ Colouring graphs with no induced six-vertex path or diamond ⋮ Locating-dominating sets: from graphs to oriented graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weighted independent sets in classes of \(P_6\)-free graphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
• On the chromatic index of multigraphs without large triangles
• The strong perfect graph theorem
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Linear recognition of pseudo-split graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• 3-colorability and forbidden subgraphs. I: Characterizing pairs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• Some applications of Vizing's theorem to vertex colorings of graphs
• Algorithmic graph theory and perfect graphs
• Vertex colouring and forbidden subgraphs -- a survey
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On a property of the class of n-colorable graphs
• Forbidden Subgraphs and 3-Colorings
• Perfect coloring and linearly χ-boundP6-free graphs
• A Linear Recognition Algorithm for Cographs
• CHROMATIC BOUNDS FOR A CLASS OF GRAPHS
• Graph Classes: A Survey
• Radius two trees specify χ‐bounded classes
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Independent Set in P₅-Free Graphs in Polynomial Time
• Sur le coloriage des graphs

This page was built for publication: Vizing bound for the chromatic number on some graph classes