On-line graph coloring of \({\mathbb{P}_5}\)-free graphs

DOI10.1007/S00236-007-0064-XzbMath1147.05028OpenAlexW2115833325MaRDI QIDQ2482722

Iwona Cieślik

Publication date: 23 April 2008

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-007-0064-x

zbMATH Keywords

clique covering on line algorithmcompetitive finctiongraphs without induced path on 5 verticeson line colouringquadratic lower bound

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Star chromatic bounds ⋮ Star coloring of certain graph classes ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dominating cliques in \(P_ 5\)-free graphs
• Effective on-line coloring of \(P_ 5\)-free graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs
• On-line and first fit colorings of graphs
• Effective coloration
• On-Line 3-Chromatic Graphs I. Triangle-Free Graphs
• Optimal on-line coloring of circular arc graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Dominating cliques in graphs

This page was built for publication: On-line graph coloring of \({\mathbb{P}_5}\)-free graphs