On-line graph coloring of P₅-free graphs

DOI10.1007/S00236-007-0064-XMaRDI QIDQ2482722zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Effective on-line coloring of \(P_ 5\)-free graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• On-line coloring of \(I_{s}\)-free graphs
• scientific article; zbMATH DE number 65699

Cites work

• Dominating cliques in \(P_ 5\)-free graphs
• Dominating cliques in graphs
• Effective coloration
• Effective on-line coloring of \(P_ 5\)-free graphs
• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On-Line 3-Chromatic Graphs I. Triangle-Free Graphs
• On-line and first fit colorings of graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs
• On-line coloring of \(I_{s}\)-free graphs
• Optimal on-line coloring of circular arc graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(8)

• Effective on-line coloring of \(P_ 5\)-free graphs
• Star coloring of certain graph classes
• Advice complexity of maximum independent set in sparse and bipartite graphs
• On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs
• An on-line competitive algorithm for coloring P₈-free bipartite graphs
• Star chromatic bounds
• -boundedness and related problems on graphs without long induced paths: a survey
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482722)