On optimal \(k\)-fold colorings of webs and antiwebs (Q1759864): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Manoel B. Campêlo / rank | |||
Property / reviewed by | |||
Property / reviewed by: Gabriel Semanisin / rank | |||
Property / author | |||
Property / author: Manoel B. Campêlo / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Gabriel Semanisin / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1562041694 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1108.5757 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 21:53, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On optimal \(k\)-fold colorings of webs and antiwebs |
scientific article |
Statements
On optimal \(k\)-fold colorings of webs and antiwebs (English)
0 references
22 November 2012
0 references
A \(k\)-fold \(x\)-colouring of a graph is an assignment of (at least) \(k\) distinct colours from the set \(\{1,2,\dots,x\}\) to each vertex such that any two adjacent vertices are assigned disjoint sets of colours. The smallest number \(x\) such that a graph \(G\) admits a \(k\)-fold \(x\)-colouring is the \(k\)th chromatic number of \(G\), denoted by \(\chi_k(G)\). The paper deals with graphs that are called webs and antiwebs, where a web is a graph \(W^n_p\) with vertex set \(\{v_0,v_1,\dots,v_n\}\), \(p\geq 1\), \(n\geq 2p\) and edge set \(\{v_i v_j:p\leq |i-j|\leq n-p\}\) and an antiweb is its complement. The authors determine exact values of the studied invariant for webs and antiwebs. The obtained results provide a generalization of the known results for odd cycles and imply necessary and sufficient conditions under which \(\chi_k (G)\) attains its lower and upper bounds based on clique and integer and fractional chromatic numbers. Moreover, the authors introduce the concept of \(\chi_k\)@-critical graphs.
0 references
\(k\)-fold graph coloring
0 references
fractional chromatic number
0 references
clique number
0 references
stable set number
0 references
web
0 references
antiweb
0 references