A proper vertex coloring \(c\) of a graph \(G\) using colors \(1,2,\dots\) is said to be minimal if \(\sum_{v\in V(G)} c(v)\) is minimum among all vertex colorings of \(G\). The vertex strength of \(G\), denoted by \(s(G)\), is the smallest number of colors needed to obtain a minimal coloring of \(G\). (The edge strength of \(G\), denoted by \(s'(G)\), is similarly defined.) The coloring number of \(G\), denoted by \(\text{col}(G)\), is the smallest number \(d\) such that for some linear ordering \(<\) of the vertex set of \(G\), the back degree \(|\{v: v<u\) and \(vu\in E(G)\}|\) of each vertex \(u\) of \(G\) is strictly less than \(d\). These notions have been studied by E. Kubicka and others in 1989-1990. In this paper, the following results are proved: (1) For any connected graph \(G\), \(s(G)= \Delta(G)+1\) if and only if \(G\) is a complete graph or an odd cycle. (2) \(s(G)\leq [{\text{col}(G)+ \Delta(G)\over 2}]\). (3) \(\Delta(G)\leq s'(G)\leq \Delta(G)+ 1\).
- An effective heuristic algorithm for sum coloring of graphs
- On sum coloring of graphs
- Minimax relations for the partial q-colorings of a graph
- Sum coloring and interval graphs: A tight upper bound for the minimum number of colors
- A branch-and-price algorithm for the minimum sum coloring problem
- Minimum degree conditions for the strength and bandwidth of graphs
- Minimum sum coloring problem: upper bounds for the chromatic strength
- On sum edge-coloring of regular, bipartite and split graphs
- Minimal colorings for properly colored subgraphs
- Tabular graphs and chromatic sum
- Weakly completable critical sets for proper vertex and edge colourings of graphs
- A tabu search approach for the sum coloring problem
- scientific article; zbMATH DE number 5904019 (Why is no real title available?)
- New variable neighborhood search method for minimum sum coloring problem on simple graphs
- Chromatic Edge Strength of Some Multigraphs
- Graphs with least number of colorings
- scientific article; zbMATH DE number 861338 (Why is no real title available?)
- A result on the strength of graphs by factorizations of complete graphs
- scientific article; zbMATH DE number 3205929 (Why is no real title available?)
- The cost chromatic number and hypergraph parameters
- A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph
- On sum edge-colorings of complete tripartite graphs
- An exact algorithm for the minimum sum coloring problem on partially decomposable graphs
- On semistrong edge-colorings of some regular graphs
- Contractions and minimal k-colorability
- A note on the strength and minimum color sum of bipartite graphs
- Minimum sum edge colorings of multicycles
This page was built for publication: Minimal coloring and strength of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1974540)
